Cloud security is gaining more and more importance in many applications and services nowadays. One of the important techniques that can be used to strengthen confidentiality of data stored in the cloud is the so-called all-or-nothing encryption. All-or-nothing encryption provides semantic security of data while guaranteeing that the data can only be recovered if and only if all blocks of a ciphertext are available for download by or known to a given client. Therefore all-or-nothing encryption does not solely rely on the secrecy of the encryption key for the data: In order to acquire any meaningful information of the input plaintext it is required that any adversary has access to all the data or blocks of the ciphertext respectively. Therefore all-or-nothing encryption ensures a transparent key management process and naturally complement information dispersal techniques that can be used to efficiently store the data in a distributed storage like cloud storage.
Conventional all-or-nothing encryptions are for example disclosed in the non-patent literature of R. Rivest, “All-or-Nothing Encryption and The Package Transform”, in Proceedings of Fast Software Encryption, pages 210-218, 1997 or in the non-patent literature of Anan Desai, “The Security of All-Or-Nothing Encryption: Protecting Against Exhaustive Key Search”, in Proceedings of CRYPTO, 2000 or in the non-patent literature of Ghassan Karame, Claudio Soriente, Krzysztof Lichota, Srdjan Capkun, “Technical Report”, available from: https://eprint.iacr.org/2014/556.pdf. Such conventional all-or-nothing encryption schemes have the following steps:                Key generation procedure: On input of a security parameter, the key generation procedure outputs an encryption key K.        Encryption procedure: On input of a plaintext p which is comprised on m blocks of size I bits each manual input of the encryption key K, the encryption procedure outputs n=m+1 blocks of ciphertext.        Decryption procedure: On input of the encryption key K and the entire ciphertext blocks a decryption procedure outputs the plaintext blocks p. If all ciphertext blocks are not available, then decryption procedure outputs NULL.        
Further conventional linear transformations are for example disclosed in the non-patent literature of D. R. Stinson, “Something About all or Nothing (Transforms)”, Designs, Codes and Cryptography, 2001.
One of the problems when outsourcing data of a cloud is that data confidentiality should be ensured in spite of a curious cloud. Another problem lies in the data availability in spite of a cloud server that can fail.
Conventional methods rely on the one hand on encryption to provide data confidentiality and on the other hand on information dispersal algorithms IDA to disperse the data into a plurality of n chunks such that any t servers can reconstruct the data. Such information dispersal only guarantees data availability in spite of failures but does not necessarily ensure data confidentiality. This means that the shares of the information dispersed by the information dispersal algorithm and which are held by each server still leak considerable information about the original plaintext.
To address this problem, so-called ramp schemes have been proposed. Such ramp schemes usually have two thresholds t1 and t2 out of n shares of data. The threshold t2 is the so-called standard reconstruction threshold which ensures data reconstructability from any t2 shares out of said n shares. The threshold t1 is the maximum number of shares that do not leak any information about the input or plaintext data. Thus, t1 is smaller than t2. Conventional information dispersal algorithm schemes are (0, t2, n) ramp schemes, since any share leaks information about the input data and therefore the threshold t1=0.
Conventionally, such ramp schemes are constructed, for example, by transforming specific information dispersal algorithm schemes, such as the Reed Solomon code to ramp schemes which is for example disclosed in the non-patent literature of H. Koga, S. Honjo, “A secret sharing scheme based on a systematic Reed-Solomon code and analysis of its security for a general class of sources”, in IEEE Symposium on Information Theory, 2014 and of McEliece, R. J. and Sarwate, D. V., “On Sharing Secrets and Reed-Solomon Codes”, Communication of the ACM September 1981.
Other conventional constructions of ramp schemes cannot be deployed or are very difficult to deploy in practice, see for example the conventional ramp schemes as disclosed in the non-patent literature of G. R. Blakley, Catherine Meadows, “Security of Ramp Schemes”, Advances in Cryptology, 1985 and of Maura B. Paterson, Douglas R. Stinson, “A simple combinatorial treatment of constructions and threshold gaps of ramp schemes”. Other conventional methods are disclosed in the already above-mentioned non-patent literature of H. Koga, S. Honjo, “A secret sharing scheme based on a systematic Reed-Solomon code and analysis of its security for a general class of sources”, in IEEE Symposium on InformationTheory, 2014 and make or need specific assumptions about the input data.